package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-05
 * Time:16:09
 */

/**
 *
 牛客算法篇:BM37 二叉搜索树的最近公共祖先
 描述
 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
 2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
 3.所有节点的值都是唯一的。
 4.p、q 为不同节点且均存在于给定的二叉搜索树中。
 数据范围:
 3<=节点总数<=10000
 0<=节点值<=10000
 如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5}，如下图:
 示例1
 输入：
 {7,1,12,0,4,11,14,#,#,3,5},1,12
 返回值：
 7
 说明：
 节点1 和 节点12的最近公共祖先是7
 */
public class lowestCommonAncestor {
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //首先，检查当前节点 root 是否为空，如果为空则返回 -1。
        if (root == null) return -1;

        //接着，检查当前节点的值是否等于节点 p 或节点 q 的值，如果是则返回当前节点的值，因为节点本身也可以是其自己的祖先。
        if(root.val==p || root.val==q) return root.val;

        //然后，分别递归在左子树和右子树中寻找节点 p 和节点 q 的最近公共祖先，分别存储在 left 和 right 中。
        int left = lowestCommonAncestor(root.left,p,q);
        int right =  lowestCommonAncestor(root.right,p,q);

        //如果左子树中找不到最近公共祖先，则返回右子树中找到的结果；如果右子树中找不到，则返回左子树中找到的结果。
        if (left == -1) return right;
        else if (right == -1) return left;

        //如果左右子树分别找到最近公共祖先，则当前节点就是它们的最近公共祖先，返回当前节点的值。
        else return root.val;
    }
}
